The present invention relates generally to digital counters and methods of counting, especially as implemented in those digital counters that use non-volatile memory.
Digital counters that retain their count for extended period of time without the need for uninterrupted power supplies are indispensable parts of modern electronics. Some typical examples of these applications are digital automotive odometers, digital usage meters for commercial appliances, and cryptographic systems that require a unique numerical tab for each transaction to prevent fraudulent system access. Non-volatile memories such as EEPROM and Flash memory, being able to store information permanently without needing any additional electrical power, should be well suited to such applications.
However, there are limitations associated with the use of non-volatile memories for counting applications. EEPROM and Flash memories are programmed and erased by injecting electrons into and discharging electrons from floating gates, which are semiconductor structures that are typically made of polysilicon. Repeated programming and erasure of a floating gate can cause charge to be trapped in the polysilicon permanently, resulting in a drift in threshold voltage over time. Eventually, these trapped electrons will prevent further reprogramming, inducing device malfunction. The maximum number of cycles a memory cell can endure before programming error is expected is commonly called the endurance cycle rating. This endurance cycle rating is typically derived through extensive characterization and qualification processes. A single programming step followed by a single erasure step constitutes a single endurance cycle. Current non-volatile memory design and fabrication technology produce EEPROM and Flash memories that have endurance cycle rating of between ten thousand to one million. In typical EEPROM implementations, writing to a group of bits may cause multiple bits within the group to xe2x80x9cexpandxe2x80x9d an endurance cycle even if their state does not change. This is because typical implementations may reset the entire group and then only set those that should set in the final state.
To facilitate description and explanation of various counting methods, we will, hereafter, adopt the following convention for memory programming and erasure: programming denotes the injection of electrons into the floating gates while erasure denotes the discharge of electrons from the floating gates. When binary representation is used, the programmed state is represented by the binary number xe2x80x9c0xe2x80x9d while the erased state will be represented by the binary number xe2x80x9c1xe2x80x9d. When a memory cell changes state from a 1 to a 0, it will hereafter be called the setting of the cell. When a memory cell changes state from a 0 to a 1, it will hereafter be called the resetting of the cell.
Because of the limitation imposed by the endurance cycles, anytime EEPROM or flash memory cells are employed as counting bits for digital counters, one must take the endurance of the memory used into account. For instance, in a typical binary counter, the least significant bit (LSB) switches from 0 to 1 or 1 to 0 for each count, the second LSB changes state every time the LSB switches from 1 to 0, the third LSB changes state every time the second LSB changes from 1 to 0 and so on. Since the LSB in a binary counter is one that changes state most, it is also the one that will usually fail first. Assuming that the EEPROM cells used for such application have an endurance cycle rating of one hundred thousand cycles, such a counter can only be expected to have a maximum count limit of about two hundred thousand, after which a counting error can be expected to occur due to programming failure of the LSB. Alternatively, the most significant bits of a binary counter may fail due to their having been repeatedly set to a zero.
Obviously, the ordinary binary counting method is not an optimal way to maximize the endurance cycles of a given EEPROM counter since for a given string of bits, the least significant bit exhausts its endurance cycles long before other bits, rendering the counter useless even though most of the bits still have plenty of endurance cycles left. To maximize the count of a given number of EEPROM cells, or to minimize the number of EEPROM cells required for a desired maximum count, one may devise a counting method that spreads out the programming cycle more evenly among all EEPROM cells. For example, counting with a Gray code number representation typically doubles the life of a counter over that of counting with the usual binary number representations.
U.S. Pat. No. 4,947,410 to Lippmann et al. entitled xe2x80x9cMethod and Apparatus for Counting with Nonvolatile Memoryxe2x80x9d and U.S. Pat. No. 6,249,562 to Wells, entitled xe2x80x9cMethod and System for Implementing a Digital Counter Optimized for Flash Memoryxe2x80x9d are typical examples of such counting methods. However, the counting methods described in the above mentioned patents require that the memories used be individually bit programmable and individually bit erasable. In other words, these methods are not applicable to an EEPROM that does not support individual bit erasure. Since most standard product EEPROM memories, such as serial EEPROM, do not support individual bit erasure, it would be desirable to have a counting method that is applicable to such memories.
Another limitation associated with the above mentioned counting methods lies in the fact that they typically require a duplicate counter to be running in parallel in order for it to recover from programming failure. It would be desirable to have a counting method that allows for recovery without the need of a redundant circuit.
It is therefore an objective of the present invention to provide a non-volatile memory based digital counter that can maximize the total count of a given counter size, considering failure possibilities, or by minimizing the number of memory cells required to reach a certain maximum count. It is another objective of the present invention to provide a counting method that can be applied to those non-volatile memories that do not support single bit erasure. It is also an objective of the present invention to provide a method of counting that enables recovery caused by write/erase failure without the need of a redundant circuit.
The present invention is a non-volatile memory based digital counter that maximizes the counting capacity of a given number of memory cells by evenly distributing the counting load among every cell and by making sure that every single change of state in every cell amounts to one count. The counter of the present invention is composed of two sub-counters: a main sub-counter, which can be an ordinary binary counter, Gray code counter or binary-coded-decimal counter operating in the usual way, and that keeps track of the more significant portion of the count, a rotary sub-counter that keeps track of the less significant portion of the count. In the rotary sub-counter, each rotation involves one setting and one resetting of all cells in the counter, with each set and each reset of a cell amounting to a single count. Such a rotary sub-counter with K number of cells will provide a total count of 2K per rotation.
The rotary sub-counter follows a pattern of changing states outlined as follow: with the cells in the rotary counter organized into groups of equal number of cells having a 1 state, the first ordinal number is represented by having the state in a first cell of a first group set to a 0 state. A subsequent set of ordinal numbers is represented by successively setting similarly positioned cells in the remaining groups of cells. A next set of ordinal numbers is being represented by resetting all but the cell in the last group back to 1s. The next two ordinal numbers are being represented by first setting a second cell in the first group to a 0 and then resetting the last cell in the previous group back to all 1s. The remainder of the ordinal numbers in the rotary set is represented by simply repeating the same pattern of cell set and reset as prescribed above until every cell in the rotary sub-counter has gone through exactly one cycle of set and reset, at which point the binary sub-counter records one count and the rotary sub-counter starts all over again, beginning with the first ordinal number being represented by the first cell pattern as described above. Because each cell gets the same number of sets and resets, the wear on the overall rotary counter is uniform.